// n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。



// 上图为 8 皇后问题的一种解法。

// 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

// 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

// 示例:

// 输入: 4
// 输出: [
//  [".Q..",  // 解法 1
//   "...Q",
//   "Q...",
//   "..Q."],

//  ["..Q.",  // 解法 2
//   "Q...",
//   "...Q",
//   ".Q.."]
// ]
// 解释: 4 皇后问题存在两个不同的解法。

#include "stdc++.h"

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result{}; //存储最终结果的数组
        vector<vector<int>> mark{};   //标记棋盘是否可以放置皇后的二维数组
        vector<string> location{};  //存储某个摆放结果，当完成一次递归找到结果后，将location push进入result
        //初始化，mark中全是0，location中是n个'.'
        for(int i{0}; i < n; ++i) {
            mark.push_back(vector<int> {});
            for(int j{0}; j < n; ++j) {
                mark[i].push_back(0);
            }
            location.push_back("");
            location[i].append(n, '.');
        }
        generate(0, n, location, result, mark);
        return result;
    }
    //k代表完成了几个皇后的位置（正在放置第k行皇后）
    void generate(int k, int n, vector<string>& location,  
                  vector<vector<string>>& result, vector<vector<int>>& mark) {
        if(k == n) {
            result.push_back(location);
            return;
        }
        for(int i{0}; i < n; ++i) {   //循环某一行的每一列
            if(mark[k][i] == 0) {  //mark数组中的值是0说明这个地方可以放置皇后
                vector<vector<int>> tmp_mark = mark;  //把当前的棋盘存下来
                location[k][i] = 'Q';
                put_down_the_queue(k, i, mark); //修改棋盘mark
                generate(k+1, n, location, result, mark);
                mark = tmp_mark;  //回溯时恢复上一步的棋盘
                location[k][i] = '.';
            }
        }
    }
private:
    void put_down_the_queue(int x, int y, vector<vector<int>>& mark) {
        static const int dx[] = {-1,1,0,0,-1,-1,1,1}; //方向数组
        static const int dy[] = {0,0,-1,1,-1,1,-1,1}; //方向数组
        mark[x][y] = 1;
        for(int i{1}; i < mark.size(); ++i) {
            for(int j{0}; j < 8; ++j) {
                int new_x = x + i*dx[j];
                int new_y = y + i*dy[j];
                if(new_x >= 0 && new_x<mark.size() && new_y >= 0 && new_y<mark.size()) {
                    mark[new_x][new_y]=1;
                }
            }
        }
    }
};

/* 基于集合的回溯

*/
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        auto solutions = vector<vector<string>>();
        auto queens = vector<int>(n, -1);
        auto columns = unordered_set<int>();
        auto diagonals1 = unordered_set<int>();
        auto diagonals2 = unordered_set<int>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) {
        if (row == n) {
            vector<string> board = generateBoard(queens, n);
            solutions.push_back(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.find(i) != columns.end()) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.find(diagonal1) != diagonals1.end()) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.find(diagonal2) != diagonals2.end()) {
                    continue;
                }
                queens[row] = i;
                columns.insert(i);
                diagonals1.insert(diagonal1);
                diagonals2.insert(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.erase(i);
                diagonals1.erase(diagonal1);
                diagonals2.erase(diagonal2);
            }
        }
    }

    vector<string> generateBoard(vector<int> &queens, int n) {
        auto board = vector<string>();
        for (int i = 0; i < n; i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};

/* 基于位运算的回溯
*/
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        auto solutions = vector<vector<string>>();
        auto queens = vector<int>(n, -1);
        solve(solutions, queens, n, 0, 0, 0, 0);
        return solutions;
    }

    void solve(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            auto board = generateBoard(queens, n);
            solutions.push_back(board);
        } else {
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                int position = availablePositions & (-availablePositions);
                availablePositions = availablePositions & (availablePositions - 1);
                int column = __builtin_ctz(position);
                queens[row] = column;
                solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) >> 1, (diagonals2 | position) << 1);
                queens[row] = -1;
            }
        }
    }

    vector<string> generateBoard(vector<int> &queens, int n) {
        auto board = vector<string>();
        for (int i = 0; i < n; i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};